\section{System-Level Synthesis Framework for 3D ICs}\label{sec:framework}

This section introduces design flow of this synthesis framework. Resource allocation, task scheduling and layer assignment methodologies are presented later in this section.

\subsection{Architecture Synthesis Framework}

Fig.~\ref{fig:framework} shows the design flow of proposed architecture
synthesis framework. Similar to 2D synthesis flow, the synthesis tool takes
task graph and component library as inputs, and outputs the optimal
architecture suggestions. Task graph is modeled using a loop-free directed
graph. Graph vertexes in the task graph represent task cells with
functionality attached. Task edge is a directed edge oriented from source cell
to destination cell showing data flow direction. Each task edge connects two
task cells through dedicated ports. The number of incoming and outgoing edges
is kept as incoming degree and outgoing degree in task cell. Component library
contains both hardware and software implementations of various functionality.

Resource allocation assigns corresponding component to each task based on
functionality requirement. After resource allocation, based on selected
components, chip area and power consumption information can be evaluated, and
the basic resource cost is calculated after resource allocation. According to the 
chip area and the function of selected components, 3D partitioning is used to
determine optimal partitioning and layer assignments. While different
partitioning methods lead to different system cost and interconnection delay,
3D floorplanning helps decide layer assignment of each function unit and
generates chip layout of each layer. Combining 3D partitioning and floorplanning
in synthesis flow can optimize chip area and mitigate heat dissipation problem which is
introduced by chip stacking. Accurate interconnect information that is obtained
from partitiong/floorplanning stage feeds to next stage for task scheduling.
The suggested synthesis results are presented in a sorted order based on the
cost function that is given according to designer's preference.

\begin{figure}
\centering
  % Requires \usepackage{graphicx}
  \includegraphics[width=0.33\textwidth]{./figures/framework.pdf}\\
  \caption{System-level Exploration Framework for 3D SoCs.}\label{fig:framework}
\end{figure}

\subsection{Resource Allocation}
In our work, genetic algorithm is used as the optimization method for resource allocation. The
advantage of genetic algorithm is that it can provide several optimized
solutions in a short time by removing solutions with high cost and leaving
other solutions to generation evolution\cite{Kenji1995}. In genetic algorithm,
a single component that can implement required functionality of one task cell
is called a gene. A DNA means a small architecture that is built with several
genes based on design principles. For example, if a software implementation of
block encoding is chosen as one gene, then memory and processors are needed as
necessary hardware support. These genes, software implementation, processors
and memories together integrate to an DNA. A set of DNAs are connected
according to architecture design principles generating a complete architecture
solution, which is called chromosome. All the implementations of task cells
construct a gene pool of the task graph. The goal of genetic algorithm is to
construct possible architectures from gene pool with minimize system cost.

At the beginning of the algorithm, a set of architectures with required
population size is initialized by randomly selecting component for each task
cell. For some cells in the task, they can be implemented either by hardware or
software. Hardware implementations are faster but with higher cost. In
contrast, software implementations are slower but it only requires memory and
processors, which provides higher flexibility. And as the number of software
usages increased, the average cost is reduced. For area and power
consideration, hardware implementations need more chip area and consume more
power. Heat dissipation problem becomes severe as more hardwares are used. For
hardware/software co-synthesis framework, resource allocation and cost function
together are trying to balance the usage between hardware and software.

The resource allocation begins with searching along task edges from source
cell. For each task cell in the task graph, control level information is
attached. The control level of source is set to 0. Control level of the task
cells grows as the graph depth is traversed from source to sink. Components are
allocated level by level beginning with the top control level. For each task
cell, the solution is randomly picked from the gene pool. Based on the selected
result, component delay information is used to calculate the finishing time for
this particular cell. The start time of each task cell is decided by the finish
time of its immediate connected task cell at previous control level.

Resource allocation has two cases based on the content of allocated component
list and their available time. New allocation is not needed once the timing
constraint is satisfied and one can reuse the components that are already
allocated. Fig.~\ref{fig:allocation outline} shows the outline of these two
cases. This allocation strategy can guarantee that task doesn't stall to wait
for available component and minimize the total number of components to increase
each component's utilization. After all task cells in task graph are assigned
with components, the cost of this architecture can be calculated.

%\begin{figure}
%\centering
%  % Requires \usepackage{graphicx}
%  \includegraphics[width=0.5\textwidth]{./figures/allocationoutline.pdf}\\
%  \caption{Genetic Algorithm Flow Chart.}\label{fig:allocation outline}
%\end{figure}

\begin{figure}[htbp]
\centering
%\scriptsize
\rule[-1mm]{0.48\textwidth}{.1pt}
\begin{codebox}
\Procname{$\proc{ResourceAllocation}(task graph)$}
\zi \Comment initialization
\li  source cell start time = 0;
\zi \Comment main loop for resource allocation
\li \While (!end of task graph)
\li \Do    search component list;
\li     \If (comp function == cell function \&\& \
\zi         comp available time $<$ cell start time)
\li       \Then  obtain comp pointer;
\li         \Else
    random select comp from comp lib;
\li    obtain comp pointer;
        \End
\li insert cell to comp task list;
\li task finish time = start time + comp delay;
\li comp available time = task finish time;
\li next cell start time = \
\zi task finish time + connection delay;
\End
\end{codebox}
\rule[1mm]{0.48\textwidth}{.1pt}
\caption{Outline of the Resource Allocation Algorithm}\label{fig:allocation outline}
\end{figure}

After the initial generation of architectures is generated, the evolution
process begins. Fig.~\ref{fig:flowchart} shows the flow chart of this genetic
algorithm. All the generated architecture solutions are sorted based on the
cost that is calculated from cost function. Among all the architecture
solutions, the first third of solutions are treated as good chromosomes and
reserved for next generation. The second part of architectures are selected to
participate in evolution. The last part of solutions are discarded and new
architectures are generated to replace them. For the architectures that are
selected for evolution, they need to go through mutation task by task. It is
randomly decided whether this task needs to be mutated. If mutation is needed,
then a new gene is selected from gene pool to replace the current one. When the
mutation process is finished, this round of evolution of an architecture is
completed.

\begin{figure}
\centering
  % Requires \usepackage{graphicx}
  \includegraphics[width=0.25\textwidth]{./figures/flowchart2.pdf}\\
  \caption{Genetic Algorithm Flow Chart.}\label{fig:flowchart}
\end{figure}

As chromosomes with high-quality genes and DNAs are kept during generation
evolution, system cost of each population gradually falls into a considerable
small range. This leads to the convergence condition of the algorithm. Cost
standard deviation is computed every time after evolution, and if the standard
deviation is under user given threshold, the convergence condition is met and
evolution process stops. In case the standard deviation can't converge to
requirement condition, the algorithm stops also after certain iteration times.
Final stopping standard deviation value is given out as feedback.

\subsection{Layer Assignment}

Layer assignment is closely related to the stacking strategy that is decided by
3D partitioning. The layer assignment is processed during 3D partitioning and
floorplanning. Designers can choose their preferred stacking strategy, or
partitioning process generates the result in the granularity of component logic
blocks. Problems concerning balanced I/O pins, optimal TSVs number and so on
can be tackled during 3D partitioning\cite{Sawicki2009}. After partitioning, 3D
floorplanning takes layer assignment of each block as input, generates virtual
layout of each layer. Various design issues, such as interconnect routing,
power/ground network\cite{Falkenstern2010} and thermal
dissipation\cite{Cong2004} are taken into account in 3D floorplanning.
Partitioning and floorplanning results affect 3D cost as well as scheduling
results. For example, if designers choose logic-to-memory stacking, then during
resource allocation, once a software implementation is allocated, the memory
that is allocated to this software is put in a different layer from other
hardware implementations. Communication delay between software implementation
and hardware implementation should be added to regular bus and port delay, and
this in turn affects the performance of the candidate architecture.

\subsection{Task Scheduling}

The task finishing time is validated through scheduling to see if the task can
meet the timing constraint. During resource allocation, the finish time of task
graph is calculated level by level. Communication delay including bus delay,
port delay and TSVs delay (if two cells are in different layers) needs to
compute during scheduling. The number of TSVs used in design has impact on
bandwidth provided between layers and thus interconnect delay reduces with more
TSVs are integrated. The ASAP(As-Soon-As-Possible) scheduling strategy is
applied to get the total execution time of this task. Once the synthesized
architecture can satisfy the timing constraint, this suggested solution is
feasible and accepted by the synthesis tool. The total latency of this task is
also a factor that influences solutions sorting.

\subsection{Cost Function}

In architecture synthesis, the cost function is key issue to determine final
architecture solutions. Basically, cost function setting is based on
experiences of designers. Different requirements about architecture generate
different cost function. It is impractical to find a universal cost function
that satisfy every aspect of consideration. Based on reality above, we use
flexible cost function formulation. The cost terms and weights for each term
are determined by designers. Equation ~\ref{eq:cost function} shows the general
form of the cost function.

\begin{equation}
\scriptsize
	\label{eq:cost function}
	Cost =\left ( \omega_1 X_1 + \omega_2 X_2 + \omega_3 X_3 \ldots + \omega_n X_n \right )+ Cost_{3D stacking}
\end{equation}

Terms in parentheses of equation~\ref{eq:cost function} is decided by user.
$\omega_n$ is the weight of each design factor. $X_n$ represents the factor
that needs to be considered during design, such as area constraint, fabrication
cost, power consumption, etc. Designers can choose to use the value of this
factor or the reverse value of this factor, $X_n \in \{f, 1/f\}$. The last term
in this equation stands for system cost of 3D IC stacking. In our work, we
mainly consider wafer-to-wafer bonding method for 3D model and TSVs for layer
communication. The cost of chip that is built using wafer-to-wafer bonding is
given in equation~\ref{eq:w2w bonding} \cite{Dong2009}. 3D cost is proportion
to the number of layers, directly related to cost of each die and cost of
bonding between layers. As the number of layers increased, total 3D cost also
increased. In addition to the number of layers, yield of each layer and yield
of 3D bonding also influence final 3D stacking cost. If area is one of the
design issues, area overhead of using TSVs should be taken into consideration.
From equation~\ref{eq:3D area} \cite{Dong2009}, it can tell that TSVs area
overhead is related to connection bandwidth between layers. The bandwidth is
determined once resource allocation and layer assignment is completed. The goal
of this synthesis tool is to minimize total cost defined by equation given by
user. By choosing suitable factors and adjusting associated weight, designers
can easily create cost function that best describes their design requirements.

\begin{equation}
	\label{eq:w2w bonding}
	C_{w2w}=\frac{\sum_{i=1}^{N}C_{die_i}+\left ( N-1 \right )C_{bonding}}{\left ( \prod_{i=1}^{N}Y_{die_i}Y_{bonding}^{N-1} \right )}
\end{equation}

\begin{equation}
	\label{eq:3D area}
	A_{3D} = A_{die} + N_{TSV/die}A_{TSV}
\end{equation}
